package com.wcj.test;

import com.wcj.linktable.ListNode;

import java.util.List;

/**
 * 给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
 * 注意是节点的编号而非节点的数值。
 *
 * 输入：
 * {1,2,3,4,5,6}
 * 返回值：
 * {1,3,5,2,4,6}
 *
 * 输入：
 * {1,4,6,3,7}
 * 返回值：
 * {1,6,7,4,3}
 */
public class 链表的奇偶重排 {

    public ListNode oddEvenList (ListNode head) {
        if (head == null){
            return head;
        }
        ListNode even = head.next;
        ListNode odd = head;
        ListNode evenhead = even;
        while (even != null && even.next != null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenhead;
        return head;
    }
}
